package numDecodings

import "strconv"

func numDecodings(s string) int {
	ans := 0
	// 以0开头的字符串的答案都是0
	if num, _ := strconv.Atoi(s[:1]); num == 0 {
		return ans
	}
	// dp[i] 第i个字符有多少种方式
	dp := make([]int, len(s)+1)
	dp[0] = 1
	dp[1] = 1 // 第一个字符有1种排列

	for i := 2; i <= len(s); i++ {
		_i2, _ := strconv.Atoi(string(s[i-2]))
		_i1, _ := strconv.Atoi(string(s[i-1]))

		// 当前字符如果不等于0
		if _i1 != 0 {
			dp[i] += dp[i-1]
		}
		// 上一个字符如果等于0，且是A-Z
		if _i2 != 0 && _i2*10+_i1 <= 26 {
			dp[i] += dp[i-2]
		}
	}
	return dp[len(s)]
}
